package com.chao.stucture.queue;

/**
 * @author : Rookie
 * @description : 一般都使用循环队列，因为顺序队列会存在假溢出问题
 * @date : 2022/11/27
 */
public class ArrayQueue<E> {

    private static final int DEFAULT_INITIAL_CAPACITY = 2 << 4;

    /**
     * 元素
     */
    private E[] array;
    /**
     * 队头指针
     */
    private int front;
    /**
     * 队尾指针
     */
    private int rear;
    /**
     * 元素个数
     */
    private int size;

    public ArrayQueue() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    public ArrayQueue(int initialCapacity) {
        this.array = (E[]) new Object[initialCapacity];
        this.front = this.rear = 0;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public boolean isFull() {
        return this.size == array.length;
    }

    /**
     * 入队一个元素
     * @param e
     */
    public void enqueue(E e) {
        if (isFull()) {
            resize(array.length * 2);
        }
        array[rear] = e;
        //队尾指针+1.
        rear = (rear + 1) % array.length;
        size ++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = array[(front + i) % array.length];
        }
        array = newData;
        front = 0;
        rear = size;
    }

    /**
     * 出队一个元素
     * @return
     */
    public E dequeue() {
        if (isEmpty()) {
            return null;
        }
        E e = array[front];
        //队头指针+1
        front = (front + 1) % array.length;
        this.size --;
        if (size < array.length / 4 && array.length > 1) {
            resize(array.length / 2);
        }
        return e;
    }

    /**
     * 查看队头元素
     * @return
     */
    public E peek() {
        return array[front];
    }

    public void print() {

        if (isEmpty()) {   // 如果队列为空，直接退出
            return;
        }

        StringBuffer sb = new StringBuffer();
        // 从头遍历到尾
        for (int i = 0; i < size; i++) {
            // 当前元素的下标
            int index = (front + i) % array.length;
            sb.append(array[index]).append(" ");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) {
        ArrayQueue<String> arrayQueue = new ArrayQueue<>();
        arrayQueue.enqueue("5");
        arrayQueue.enqueue("3");
        arrayQueue.enqueue("1");
        arrayQueue.enqueue("8");
        arrayQueue.print();
        System.out.println("队头元素是：" + arrayQueue.peek());
        System.out.println("元素" + arrayQueue.dequeue() + "出队");
        arrayQueue.print();
    }
}
